def knownMessageFormatUnkownAtEnd(prefix,e,n,c,eps=1/8):
    # Solves for message if you know the prefix of the message, such that message = prefix+x
    # It requires that x < N
    ZmodN = Zmod(n)
    C = ZmodN(c)
    prefix = ZmodN(prefix)
    P.<x> = PolynomialRing(ZmodN)
    pol = (prefix+x)^e - C
    diff = pol.small_roots(epsilon=eps)
    if(len(diff)==0):
        print("No solutions found")
        return -1
    return m+diff[0]

def knownMessageFormat(message,e,c,n,unknownEndBitIndex,eps=1/15):
    """
    unknownEndBitIndex is measured from the LSB being bit #0
    if unknownEndBitIndex is 0, it is knownMessageFormatUnkownAtEnd, but with epsilon solving capabilities.
    """
    #TODO EPSILON SOLVING CAPABILITIES
    ZmodN = Zmod(n)
    c = ZmodN(c)
    e = ZmodN(e)
    message = ZmodN(message)
    P.<x> = PolynomialRing(ZmodN)
    pol = ((message + ZmodN((pow(2,unknownEndBitIndex)))*x)^e) - c
    pol = pol.monic()

    xval = pol.small_roots(epsilon=eps)
    if(len(xval)==0):
        print("No solutions found")
        return -1
    xval = xval[0]
    xval = xval*(2**unknownEndBitIndex)
    return Integer(message+xval)

def testKnownMessageFormat():
    msg = "this challenge was supposed to be babyrsa but i screwed up and now i have to redo the challenge.\nhopefully this challenge proves to be more worthy of 250 points compared to the 200 points i gave out for babyrsa :D :D :D\nyour super secret flag is: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\nyou know what i'm going to add an extra line here just to make your life miserable so deal with it"
    msg = msg.replace('X','\x00')
    import binascii
    message = int(binascii.hexlify(msg),16)
    e = 5
    c = 321344338551168130701947757669249162791535374419225256466002854387287697945811581844875867845545337575193797350159207497966826027124926618458827324785590115214765980153475875175895244152171945352397663605222668892070894285036685408001675776259216704639659684767335997326195127379070104670798191048101430782486785148455557975065509824478935393935463232461294974471055239751453456270779997852527271795223623224696998441762750417393944955667837832299195592347653873362173157136283926817115042942127695355760288879165245940595259284499711202547364332122472169897570069773912201877037737474884548477516093671861643329899650704311880900221217905929830674467383904928054908475945599046498840246878554674443087280023564313470872269644230953001876937807402083390603760508851259383686896871724061532464374712413952574633098739843484563001012414107193262431117290853995664646176812763789444386869148000606985026530596652927567162641583951775993815884965569050328445927871220492529331846189285588168127051152438658813934744257031316581112434690871286836998078235766836485498780504037745116357109237384369621143931229920342036890494878183569174869563857473355851368119174926388706612127773670862261189669510108216517652686402185979222505401328291
    n = 805467500635696403604126524373650578882729068725582344971555936471728279008969317394226798274039587275908735628164913963756789131471531490012281262137708844664619411648776174742900969650281132608104486439462068493207388096754400356209191212924158917441463852311090597438686723680422989566039830705971272945580630621308622704812919416445637277433384864510484266136345300166188170847768250622904194100556098235897898548354386415341541887443486684297114240486341073977172459860420916964212739802004276614553755113124726331629822694410052832980560107812738167277181748569891715410067156205497753620739994002924247168259596220654379789860120944816884358006621854492232604827642867109476922149510767118658715534476782931763110787389666428593557178061972898056782926023179701767472969849999844288795597293792471883445525249025377326859655523448211020675915933552601140243332965620235850177872856558184848182439374292376522160931072677877590262080551636962148104050583711183119856867201924407132152091888936970437318064654447142605921825771487108398034919404885812834444299826080204996660391375038388918601615609593999711720104533648851576138805705999947802739408729788376315233147532770988216608571607302006681600662261521288802804512781133
    unknownEndBitIndex = Integer(8*(len(msg)-msg.rfind('\x00')-1))
    return (binascii.unhexlify(hex(knownMessageFormat(message,e,c,n,unknownEndBitIndex))))
# testKnownMessageFormat()
